//给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
//
// 返回这三个数的和。
//
// 假定每组输入只存在恰好一个解。
//
//
//
// 示例 1：
//
//
//输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
//
//
// 示例 2：
//
//
//输入：nums = [0,0,0], target = 1
//输出：0
//解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
//
//
//
// 提示：
//
//
// 3 <= nums.length <= 1000
// -1000 <= nums[i] <= 1000
// -10⁴ <= target <= 10⁴
//
//
// Related Topics 数组 双指针 排序 👍 1758 👎 0

import enums.Way;

import java.util.Arrays;

/**
 * 最接近的三数之和
 */
public class ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target, Way way) {
        if (nums == null || nums.length < 3){
            throw new IllegalArgumentException("nums is null or length < 3.");
        }
        switch (way){
            case WAY1:
                return way1(nums, target);
            case WAY2:
                return way2(nums, target);
            case WAY3:
                return way3(nums, target);
            default:
                throw new IllegalArgumentException("Way is not exist.");
        }
    }

    /**
     * 暴力求解
     * 时间复杂度：O(n³)
     * 空间复杂度：O(1)
     */
    private static int way1(int[] nums, int target){
        int best = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j < nums.length; j++){
                for (int k = j + 1; k < nums.length; k++){
                    int sum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(sum - target) < Math.abs(best - target)){
                        best = sum;
                    }
                    if (sum == target){
                        return sum;
                    }
                }
            }
        }
        return best;
    }

    /**
     * 双指针
     * 时间复杂度：O(n²)
     * 空间复杂度：O(1)
     */
    private static int way2(int[] nums, int target){
        int best = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(best - target)){
                    best = sum;
                }
                if (sum == target){
                    return sum;
                }else if (sum < target){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return best;
    }

    /**
     * 优化双指针
     * 时间复杂度：O(n²)
     * 空间复杂度：O(1)
     */
    private static int way3(int[] nums, int target){
        int best = Integer.MAX_VALUE;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(best - target)){
                    best = sum;
                }
                if (sum == target){
                    return sum;
                }else if (sum < target){
                    left++;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                }else{
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return best;
    }
}
